This invention is directed to an expandable data switching fabric using a shared memory architecture. Data is commutated with respect to both space and time to facilitate input and output of multiple high speed switched data streams without data loss.
Considerable attention has been devoted to the study of interconnection networks. See, for example, T. Feng., xe2x80x9cA Survey of Interconnection Networksxe2x80x9d, IEEE Computer, December 1991, pp. 12-27. Several network topologies have been proposed for designing parallel computers and computer communication networks.
A static interconnection network is characterized by point-to-point links which connect various nodes based upon a given structure. Common examples of static interconnection network topologies include bus, ring, mesh, crossbar, tree, hypercube and hypercycle topologies. Many static interconnection networks are multi-stage networks having no central or shared memory for storing the data which passes through the network. Additionally, most static interconnection networks have statically allocated resources for switching data through the network.
Typically, data is passed through a prior art static interconnection network by time-dividing the data path into a number of discrete sub-paths, with each sub-path being used during a specific, corresponding time slice. See, for example, U.S. Pat. Nos. 3,956,593; 4,005,272; and, 4,038,497. By contrast, the present invention passes data by dynamically allocating the network""s data switching resources and by time-dividing the data such that the entire data path can be used during all time slices.
Another prior art approach uses a shared memory architecture. Typically, a content-addressable central, shared memory is used, but without commutation. See, for example, U.S. Pat. No. 5,513,134. Prior art techniques for commutation of switched data have also been devised, as exemplified by U.S. Pat. No. 5,168,492. However, the ""492 patent uses a rotator to commutate the data, whereas the present invention employs a barrel shifter and commutates the data with respect to both space and time.
In accordance with the preferred embodiment, the invention provides a method of switching n data streams for input and output of the data streams by an n input, n output data store without data loss. This is accomplished by dividing the data store into n separate storage arrays and dividing each of the data streams into n equal-sized pieces. Then, during each one of n separate time units, one of the data stream pieces is written into a corresponding one of the storage arrays; or, one of the data stream pieces is read from a corresponding one of the storage arrays.
Preferably, for each data stream, during each time unit i, where 1xe2x89xa6ixe2x89xa6n, an ith data stream piece is written into an ith one of the storage arrays, or an ith piece is read from an ith storage array. During each jth time unit, where 1xe2x89xa6jxe2x89xa6n, one data stream piece Pij is written into an ith storage array, or one piece Pij is read from an ith storage array.
Advantageously, before the writing or reading step, each data stream is shifted in log2n separate stages, with each shifting stage respectively comprising shifting each one of the data streams by:
2(log2n)xe2x88x921 bits in the first shifting stage;
2(log2n)xe2x88x922 bits in the second shifting stage; . . . ; and,
1 bit in the nth shifting stage.
The invention further provides apparatus for switching n data streams for input and output of the data streams without data loss. The apparatus incorporates an n input, n output data store subdivided into n separate storage arrays; means for dividing each data stream into n equal-sized pieces and for writing each piece into a corresponding one of the storage arrays during each one of n separate time units; and, means for reading each written piece from the respective storage arrays during each one of another n separate time units and for combining the read pieces to reform a corresponding one of the data streams.
The means for dividing the data streams and for writing the pieces, and the means for reading the written pieces and for combining the read pieces, may each comprise a shifting means for shifting each data stream in log2n separate stages, with each shifting stage respectively comprising shifting each one of the data streams by:
2(log2n)xe2x88x921 bits in the first shifting stage;
2(log2n)xe2x88x922 bits in the second shifting stage; . . . ; and,
1 bit in the nth shifting stage.